package leetcode.solveNQueens.N皇后;

import java.util.Date;
import java.util.Scanner;


/**
 * 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，
 * 即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
 * 下面使用递归方法解决
 */
public class solveNQueensCopy {
    //使用常量来定义，方便之后解N皇后问题
    private static int count = 0;            //结果计数器

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Date begin = new Date();
        //初始化棋盘，全部置0
        short chess[][] = new short[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                chess[i][j] = 0;
            }
        }

        putQueenAtRow(chess, 0, n);
        Date end = new Date();
        System.out.println("解决 " + n + " 皇后问题，用时：" + String.valueOf(end.getTime() - begin.getTime()) + "毫秒，计算结果：" + count);
    }

    private static void putQueenAtRow(short[][] chess, int row, int n) {
        /**
         * 递归终止判断：如果row==N，则说明已经成功摆放了8个皇后
         * 输出结果，终止递归
         */
        if (row == n) {
            count++;
            System.out.println("第 " + count + " 种解：");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(chess[i][j] + " ");
                }
                System.out.println();
            }
            return;
        }

        short[][] chessTemp = chess.clone();

        /**
         * 向这一行的每一个位置尝试排放皇后
         * 然后检测状态，如果安全则继续执行递归函数摆放下一行皇后
         */
        for (int i = 0; i < n; i++) {
            //摆放这一行的皇后，之前要清掉所有这一行摆放的记录，防止污染棋盘
            for (int j = 0; j < n; j++)
                chessTemp[row][j] = 0;
            chessTemp[row][i] = 1;

            if (isSafety(chessTemp, row, i, n)) {
                putQueenAtRow(chessTemp, row + 1, n);
            }
        }
    }

    private static boolean isSafety(short[][] chess, int row, int col, int n) {
        //判断中上、左上、右上是否安全
        int step = 1;
        while (row - step >= 0) {
            if (chess[row - step][col] == 1)                //中上
                return false;
            if (col - step >= 0 && chess[row - step][col - step] == 1)        //左上
                return false;
            if (col + step < n && chess[row - step][col + step] == 1)        //右上
                return false;

            step++;
        }
        return true;
    }
}
